import java.util.*;
public class GraphSearch {
        
        static int maxFlow; 
        static boolean path = false;
       
        public GraphSearch() {
                super();
        }

/** Given a simple graph G and a source and destination vertices, this methods computed breadh first search 
 * and returns the corresponding path . The parameter d is the scaling factor where the path of atleast 
 * value d is computed. If d is set to 0 , this method is equivalent to the traditional DFS.
 * @param G :  A simple graph G on which the DFS is computed
 * @param s : Source vertex from which the search is initiated
 * @param t : The destination vertex to which the path is computed
 * @param d : The scaling factor . The search is conducted on edges of min capacity d
 * @param p : The return path is sent through this reference.
 */
        public static SimpleGraph depthFirstSearch (SimpleGraph G, Vertex s, Vertex t, SimpleGraph stpath, int scale) {
                Vertex v;
                Edge e;
                Iterator i;
                SimpleGraph newPath;
                path = false;

                ((VertexData) s.getData()).setVisited(true);
                stpath.vertexList.add(s);
              

                for (i= G.incidentEdges(s); i.hasNext(); ) {
                        e = (Edge) i.next();
                        v = G.opposite(s, e);
                        
                        if (!( (VertexData) v.getData()).isVisited() &&
                               (v == e.getSecondEndpoint() && ((EdgeData) e.getData()).getForwardCapacity() > scale||
                                v == e.getFirstEndpoint() && ((EdgeData) e.getData()).getBackwardCapacity() > scale)) {
                                
                               if (v == t)
                               {                                        
                            	   		stpath.edgeList.add(e);
                                        stpath.vertexList.add(v);
                                        return stpath;
                                }

                                stpath.edgeList.add(e);
                               
                                newPath = depthFirstSearch(G, v, t, stpath, scale);
                                if (newPath.vertexList.getLast() == t) {
                                        maxFlow((EdgeData) ((Edge) newPath.edgeList.getFirst()).getData());
                                        isPath();
                                        return newPath;
                                }
                                
                                stpath.edgeList.removeLast();
                        }
                        ( (VertexData) s.getData()).setVisited(true);
                }

                stpath.vertexList.removeLast();
                return stpath;
        }

        private static Boolean isPath() {
                return path = true;
                
        }

        private static int maxFlow(EdgeData data) {
                maxFlow =+ data.getFlow();
                return maxFlow;
                
        }
/**
 * The main method is included to test the DFS method . When passed a graph object
 * it is returning the s-t path, which is printed for clarity.
 * @param args
 * @throws Exception
 */
        public static void main(String[] args) throws Exception {
                SimpleGraph G = new SimpleGraph();
                Vertex v;
                Edge e;
                SimpleGraph path;
                Iterator i;
                EdgeData edata;
                VertexData vdata;
                
        		GraphInput.LoadSimpleGraph(G, "/home/iyer/Algorithms/Project/b2.txt");
        		GraphConversion.ConvertGraph(G);
                for (i = G.vertices(); i.hasNext(); ){
                        v = (Vertex) i.next();
                        vdata = (VertexData) v.getData();
                        vdata.setVisited(false);                        
                }
        		path = depthFirstSearch(G, (Vertex)G.vertexList.getFirst(), (Vertex)G.vertexList.getLast(), new SimpleGraph(),2);
              
                System.out.println("Path found:");
                for (i = path.edges(); i.hasNext(); ){
                        e = (Edge) i.next();
                        edata = (EdgeData) e.getData();
                        System.out.println("Edge: " + e.getName() + " " 
                                        + e.getFirstEndpoint().getName() + "-" 
                                        + e.getSecondEndpoint().getName() + " "
                                        + edata.getFlow() + "/" + edata.getCapacity());
                }
                System.out.println();
                
            
        }
}
